import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LoadingProblem {
    /**
     * 装载问题的回溯方法
     * 用回溯法编写一个递归程序解决如下装载问题：
     * 有 n 个集装箱要装上 2 艘载重分别为 c1 和 c2的轮船，其中集装箱 i 的重量为 wi（1≤ i ≤ n），且∑ 𝑤𝑖 ≤ 𝑐1 + 𝑐2 𝑛 𝑖=1 。
     * 问是否有一个合理 的装载方案可以将这 n 个集装箱装上这 2 艘轮船？
     * 如果有，请给出装载方案。
     * 举例：当 n=3，c1=c2=50，且 w=[10,40,40]时，
     * 可以将集装箱 1 和 2 装到第一艘轮船上，集装箱 3 装到第二艘轮船上；如果 w=[20,40,40]时，无法将这 3 个集装箱都装上轮船。
     */

    /**
     * 回溯函数
     * @param weights
     * @param c1
     * @param c2
     * @param index
     * @param used
     * @param solution
     * @return
     */
    public static boolean backtrack(int[] weights, int c1, int c2, int index, boolean[] used, List<Integer> solution){
        if(index==weights.length){
            return true;
        }

        // 尝试将当前的集装箱放入第一个轮船
        if(weights[index]<=c1){
            used[index]=true;
            if(backtrack(weights, c1-weights[index], c2, index+1, used, solution)){
                solution.add(index+1);
                return true;
            }
            used[index]=false;
        }

        // 尝试将当前集装箱放入第二艘轮船
        if (weights[index] <= c2) {
            used[index] = true;
            if (backtrack(weights, c1, c2 - weights[index], index + 1, used, solution)) {
                solution.add(index + 1);
                return true;
            }
            used[index] = false;
        }

        // 不放入任何轮船
        if(backtrack(weights, c1, c2, index+1, used, solution)){
            return true;
        }

        return false;
    }

    public static List<Integer> findLoadingSolution(int[] weights, int c1, int c2) {
        List<Integer> solution = new ArrayList<>();
        boolean[] used = new boolean[weights.length];
        Arrays.fill(used, false);

        if (backtrack(weights, c1, c2, 0, used, solution)) {
            return solution;
        }

        return new ArrayList<>();
    }

    public static void main(String[] args) {
        int[] weights = {20, 40, 40};
        int c1 = 50;
        int c2 = 50;

        List<Integer> solution = findLoadingSolution(weights, c1, c2);

        if (solution.isEmpty()) {
            System.out.println("无法将所有集装箱装上轮船。");
        } else {
            System.out.println("可以将以下集装箱装上轮船：");
            for (int i : solution) {
                System.out.println("集装箱 " + i + " "+weights[i]);
            }
        }
    }

}
